Garbage collection

From OSDev Wiki
Jump to navigation Jump to search

Garbage Collection (GC) is a memory management technique frequently used in high-level languages that allows the programmer not to worry about when memory areas should be returned to the system. Virtually all the object-oriented languages introduced after C++ provide some way of garbage collection (including Python, Java, Objective C). It can also be found in LISP or PERL, for instance.

How does it work?

Reference counting

The most basic implementation of garbage collection uses reference counting: each object is associated with a counter that tells how many other objects refer to it. Say for instance you have a Disk object, every time your system needs another reference to that object (for instance because the DiskPartition object has a reference to the parent Disk object), the reference counter of Disk is incremented. Of course, if programmed manually, this is tedious and bugprone (although in C++ at least, the use of smart pointers can automate this bookkeeping). Plus GC's solely based on reference counting will be unable to free self-referencing (or circular) structures, meaning that memory leaks are possible.

Mark & Sweep

A mark-sweep garbage collector traverses all reachable objects in the heap by following pointers beginning with the "roots", i.e. pointers stored in statically allocated or stack allocated program variables (and possibly registers as well, depending on the GC implementation). All such reachable objects are marked. A sweep over the entire heap is then performed to restore unmarked objects to a free list, so they can be reallocated.

Drawn from Hans Boehm's texts, see links below.

Copy collectors

In contrast, a copying collector copies reachable objects to another region of memory as they are being traversed. Provided the traversal is done in breadth first order, there is a well-known and simple algorithm for performing this traversal without auxiliary storage or recursion. After such a traversal all surviving objects reside in a contiguous region of memory, and all pointers have been updated to point to the new object locations. The previously used region of memory can then be reused in its entirety. Allocation becomes trivial, since all free space is always contiguous.

During the process, the GC builds an object graph to track the "live" objects so that it can update references to any objects that it moves. This means that with a compacting GC, there is no extra level of indirection required in order to move objects around in memory. It also means that programmers cannot rely on the values of references remaining stable during execution of their program, which is one reason why languages such as Java and C# disallow pointer arithmetic on references to garbage collected objects.

A variant of compacting collectors is the generational garbage collector where the memory is partitioned among recently-created objects and longer-lived objects. If an object remains present in the "recently-created" heap for N sweeps of the GC, it is then moved to the "longer-lived" heap. This technique is used by some JVMs and the .NET CLR to reduce the cost of heap-sweeping as the heap grows larger. It is based on the assumption that a long-lived object is less likely to become garbage and thus that the "long-lived objects" heap could be swept with lower frequency.

One of the major advantages of a compacting collector is that it makes allocating from the heap extremely fast and scalable to multiprocessor systems. All you have to do to allocate a new object is to increment a "top-of-heap" pointer and initialize a few fields, which can be done in constant time. A primitive malloc() would, in comparison, have to scan the free block list to find a block large enough to satisfy the request, with a worst-case complexity of O(n) (n being the number of free blocks), all the while holding a global heap lock – not a Good Ideatm in a multithreading system. (Modern malloc() implementations use a number of techniques to reduce the impact of this, and achieve O(1) behaviour for most cases.)

On the other hand, most compacting collectors need to "stop the world" (i.e. suspend all threads) during a collection so that they can safely move objects around. This makes them very unsuitable for use in a real-time system, and that most likely includes OS kernels as well.

Can I use garbage collection in my OS?

There isn't a real agreement on that among the community. Some says you shouldn't even think about it, other says it is fully possible. If this is your very first OS and unless you start your OS with the goal of proving that a garbage collector in kernel land is possible and better than by-hand memory management, then probably you shouldn't mess with garbage collection.

Whatever you chose to do, make sure that your garbage collector implementation is fully tested and stressed in a host environment before moving it into kernel space. And that missing a few garbage items is probably better than collecting live items :P

The "Singularity" project (Microsoft Research, closed-source) and the FlingOS (educational OS, open-source) both use GC everywhere including in the kernel, so it can be done. Yet it needs to be done properly and it has important implications on your kernel design:

  • Using a single garbage-collected heap for every chunk of memory (both kernel and user) is probably a Bad Thingtm. You are most likely to have collected kernel-wide heap, collected process(/thread)-pinned heap(s) and uncollected kernel heap.
  • Having the garbage-collector freeze everything to work is unacceptable at kernel level, yet not all GC's require this (concurent mark & sweep being an example).
  • Garbage collection is often coupled with strong object typing and important restrictions on pointers arithmetic which might not be practical in C/C++ ... still under discussion.

References

Forum

Websites

Retrieved from "https://wiki.osdev.org/index.php?title=Garbage_collection&oldid=19321"